﻿#include "pch.h"
#include "CppUnitTest.h"
#include "../ForTest.h"

using namespace Microsoft::VisualStudio::CppUnitTestFramework;



namespace PreSum3
{
	TEST_CLASS(LC813)
	{
		//LC813. 最大平均值和的分组
		class Solution {
		public:
			double largestSumOfAverages(vector<int>& nums, const int K) {
				const int N = nums.size();
				vector<int> preSum(1);
				for (const auto& n : nums) {
					preSum.emplace_back(n + preSum.back());
				}
				vector<vector<double>> dp(N + 1, vector<double>(K+1,-1e9));
				dp[0][0] = 0;
				for (int i = 0; i < N; i++) {
					for (int k = 0; k < K; k++) {
						for (int j = i + 1; j <= N; j++) {
							dp[j][k + 1] = max(dp[j][k + 1],dp[i][k] + ((double)preSum[j]- preSum[i])/(j-i));
						}
					}
				}
				return dp.back().back();
			}
		};
	public:
		vector<int> nums;
		int k;
		TEST_METHOD(TestMethod11)
		{
			nums = { 9, 1, 2, 3, 9 }, k = 3;
			auto res = Solution().largestSumOfAverages(nums, k);
			AssertEx(20.0, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 1,2,3,4,5,6,7 }, k = 4;
			auto res = Solution().largestSumOfAverages(nums, k);
			AssertEx(20.5, res);
		}
	};

	TEST_CLASS(LC1737)
	{
		//LC1737. 满足三条件之一需改变的最少字符数
		class Solution {
		public:
			int minCharacters(string a, string b) {
				const int N1 = a.length();
				const int N2 = b.length();
				int cnta[26] = { 0 }, cntb[26] = { 0 }, cnt[26] = { 0 };
				for (const auto& ch : a) {
					cnta[ch - 'a']++;
					cnt[ch - 'a']++;
				}
				for (const auto& ch : b) {
					cntb[ch - 'a']++;
					cnt[ch - 'a']++;
				}
				int ret = INT_MAX;
				auto Fun1 = [&](int* cnta, int* cntb,const int N) {
					int cnt1 = 0, cnt2 = 0;
					for (int i = 0; i < 25; i++) {
						cnt1 += cnta[i];
						cnt2 += cntb[i];
						ret = min(ret, N - cnt1 + cnt2);//方式一						
					}
				};
				Fun1(cnta, cntb,N1);
				Fun1(cntb, cnta,N2);
				ret = min(ret, N1+N2 - *std::max_element(cnt,cnt+26));
				return ret;
			}
		};
	public:
		string a,b;
		TEST_METHOD(TestMethod1)
		{
			a = "dee", b = "a";
			auto res = Solution().minCharacters(a, b);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod11)
		{
			a = "aba", b = "caa";
			auto res = Solution().minCharacters(a, b);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod12)
		{
			a = "dabadd", b = "cda";
			auto res = Solution().minCharacters(a, b);
			AssertEx(3, res);
		}
	};
	TEST_CLASS(LC1140)
	{
		//LC1140. 石子游
		class Solution {
		public:
			int stoneGameII(vector<int>& piles) {
				vector<int> preSum(1);
				for (const auto& n : piles) {
					preSum.emplace_back(n + preSum.back());
				}
				const int N = piles.size();
				vector<vector<int>> dp(N + 1, vector<int>(N + 1, 0));
				for (int i = N - 1; i >= 0; i--) {
					for (int m = 1; m <= N; m++) {
						int& cur = dp[i][m];
						for (int x = 1; (x <= m) && (i + x <= N); x++) {
							int m1 = max(2 * x, m);
							m1 = min(m1, N);
							cur = max(cur, preSum.back() - preSum[i] - dp[i + x][m1]);
						}

					}
				}			
				return dp[0][min(2,N)];
			}
		};
	public:
		vector<int> piles;
		TEST_METHOD(TestMethod1)
		{
			piles = { 1};
			auto res = Solution().stoneGameII(piles);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod2)
		{
			piles = { 1,2 };
			auto res = Solution().stoneGameII(piles);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod3)
		{
			piles = { 1,2,3 };
			auto res = Solution().stoneGameII(piles);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod4)
		{
			piles = { 1,2,3,4 };
			auto res = Solution().stoneGameII(piles);
			AssertEx(5, res);
		}
		TEST_METHOD(TestMethod11)
		{
			piles = { 2, 7, 9, 4, 4 };
			auto res = Solution().stoneGameII(piles);
			AssertEx(10, res);
		}
		TEST_METHOD(TestMethod12)
		{
			piles = { 1,2,3,4,5,100 };
			auto res = Solution().stoneGameII(piles);
			AssertEx(104, res);
		}

	};
	TEST_CLASS(LC2245)
	{
		//LC2245. 转角路径的乘积中最多能有几个尾随零
		class Solution {
		public:
			int maxTrailingZeros(vector<vector<int>>& grid) {
				m_iR = grid.size();
				m_iC = grid[0].size();
				auto Cnt2 = [&](int r, int c) {
					int tmp = grid[r][c];
					int cnt = 0;
					for (; (0 == tmp % 2); tmp /= 2, cnt++);
					return cnt;
				};
				auto Cnt5 = [&](int r, int c) {
					int tmp = grid[r][c];
					int cnt = 0;
					for (; (0 == tmp % 5); tmp /= 5, cnt++);
					return cnt;
				};
				int ret = 0;
				CPreSum2<int> preSum2(m_iR, m_iC, Cnt2);
				CPreSum2<int> preSum5(m_iR, m_iC, Cnt5);
				for (int r = 0; r < m_iR; r++) {
					for (int c = 0; c < m_iC; c++) {
						if( (r > 0 )&&( c > 0 ))
						{//左上 
							const int ctn2 = preSum2.Get(0, r, c, r) + preSum2.Get(c,0,c,r-1);
							const int ctn5 = preSum5.Get(0, r, c, r) + preSum5.Get(c, 0, c, r - 1);
							ret = max(ret, min(ctn2, ctn5));
						}
						if ((r + 1 != m_iR) && (c > 0)) {//左下
							const int ctn2 = preSum2.Get(0, r, c, r) + preSum2.Get(c, r+1, c, m_iR-1);
							const int ctn5 = preSum5.Get(0, r, c, r) + preSum5.Get(c, r + 1, c, m_iR - 1);
							ret = max(ret, min(ctn2, ctn5));
						}
						if ((r > 0) && (c+1 != m_iC ))
						{//右上 
							const int ctn2 = preSum2.Get(c, r, m_iC-1, r) + preSum2.Get(c, 0, c, r - 1);
							const int ctn5 = preSum5.Get(c, r, m_iC - 1, r) + preSum5.Get(c, 0, c, r - 1);
							ret = max(ret, min(ctn2, ctn5));
						}
						if ((r + 1 != m_iR) && (c + 1 != m_iC)) {//右下
							const int ctn2 = preSum2.Get(c, r, m_iC - 1, r) + preSum2.Get(c, r + 1, c, m_iR - 1);
							const int ctn5 = preSum5.Get(c, r, m_iC - 1, r) + preSum5.Get(c, r + 1, c, m_iR - 1);
							ret = max(ret, min(ctn2, ctn5));
						}
						{//水平
							const int ctn2 = preSum2.Get(0, r, m_iC - 1, r) ;
							const int ctn5 = preSum5.Get(0, r, m_iC - 1, r);;
							ret = max(ret, min(ctn2, ctn5));
						}
						{//竖直
							const int ctn2 = preSum2.Get(c, 0, c, m_iR-1);
							const int ctn5 = preSum5.Get(c, 0, c, m_iR - 1);
							ret = max(ret, min(ctn2, ctn5));
						}
					}
				}
				return ret;
			}
			int m_iR, m_iC;
		};
	public:
		vector<vector<int>> grid;
		TEST_METHOD(TestMethod11)
		{
			grid = { {23,17,15,3,20},{8,1,20,27,11},{9,4,6,2,21},{40,9,1,10,6},{22,7,4,5,3} };
			auto res = Solution().maxTrailingZeros(grid);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod12)
		{
			grid = { {4,3,2},{7,6,1},{8,8,8} };
			auto res = Solution().maxTrailingZeros(grid);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod13)
		{
			grid = { {1,5,2,4,25} };
			auto res = Solution().maxTrailingZeros(grid);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod14)
		{
			grid = { {2},{5},{10} };
			auto res = Solution().maxTrailingZeros(grid);
			AssertEx(2, res);
		}
	};
	TEST_CLASS(LC1590)
	{
		//LC1590. 使数组和能被 P 整除
		class Solution {
		public:
			int minSubarray(vector<int>& nums, int p) {
				const int N = nums.size();
				vector<int> preSum(1);
				for (const auto& n : nums) {
					preSum.emplace_back((n + preSum.back()) % p);
				}
				const int p1 = preSum.back() % p;
				if (0 == p1) { return 0; }
				unordered_map<int, int> mValueIndex;
				int ret = N;
				for (int j = 0; j < N; j++) {
					mValueIndex[preSum[j]] = j;
					const int p3 = (preSum[j + 1] - p1 + p) % p;
					if (mValueIndex.count(p3)) {
						ret = min(ret, j + 1 - mValueIndex[p3]);
					}
				}
				return (N == ret) ? -1 : ret;
			}
		};
	public:
		vector<int> nums;
		int p;
		TEST_METHOD(TestMethod11)
		{
			nums = { 3, 1, 4, 2 }, p = 6;
			auto res = Solution().minSubarray(nums, p);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 6,3,5,2 }, p = 9;
			auto res = Solution().minSubarray(nums, p);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod13)
		{
			nums = { 1,2,3 }, p = 3;
			auto res = Solution().minSubarray(nums, p);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod14)
		{
			nums = { 1,2,3 }, p = 7;
			auto res = Solution().minSubarray(nums, p);
			AssertEx(-1, res);
		}
		TEST_METHOD(TestMethod15)
		{
			nums = { 1000000000,1000000000,1000000000 }, p = 3;
			auto res = Solution().minSubarray(nums, p);
			AssertEx(0, res);
		}
	};

	TEST_CLASS(LC1371)
	{
		//LC1371. 每个元音包含偶数次的最长子字符串
		class Solution {
		public:
			int findTheLongestSubstring(string s) {
				unordered_map<char, int> mCharMask;
				mCharMask['a'] = 1;
				mCharMask['o'] = 2;
				mCharMask['e'] = 4;
				mCharMask['i'] = 8;
				mCharMask['u'] = 16;
				vector<int> preSum(1);
				for (const auto& ch: s) {
					preSum.emplace_back(mCharMask[ch] ^ preSum.back());
				}
				int ret = 0;
				unordered_map<int, int> mValueIndex;
				for (int j = 0; j < s.length(); j++) {
					mValueIndex.emplace(preSum[j], j);
					if (mValueIndex.count(preSum[j + 1])) {
						ret = max(ret, j + 1 - mValueIndex[preSum[j + 1]]);
					}
				}
				return ret;
			}
		};
	public:
		string s;
		TEST_METHOD(TestMethod11)
		{
			s = "eleetminicoworoep";
			auto res = Solution().findTheLongestSubstring(s);
			AssertEx(13, res);
		}
		TEST_METHOD(TestMethod12)
		{
			s = "leetcodeisgreat";
			auto res = Solution().findTheLongestSubstring(s);
			AssertEx(5, res);
		}
		TEST_METHOD(TestMethod13)
		{
			s = "bcbcbc";
			auto res = Solution().findTheLongestSubstring(s);
			AssertEx(6, res);
		}
	};
	TEST_CLASS(LC2845)
	{
		//LC2845. 统计趣味子数组的数目
		class Solution {
		public:
			long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {
				vector<int> preSum(1);
				for (const auto& n : nums) {
					const auto tmp = (k == n % modulo) + preSum.back();
					preSum.emplace_back(tmp% modulo);
				}
				unordered_map<int, int> mValueCount;
				long long ret = 0;
				for (int j = 0; j < nums.size(); j++) {
					mValueCount[preSum[j]]++;
					const int k2 = (preSum[j + 1] + modulo - k) % modulo;
					ret += mValueCount[k2];
				}
				return ret;
			}
		};
	public:
		vector<int> nums;
		int modulo,  k;
		TEST_METHOD(TestMethod1)
		{
			nums = { 4,5 }, modulo = 1, k = 0;
			auto res = Solution().countInterestingSubarrays(nums, modulo, k);
			AssertEx(3LL, res);
		}
		TEST_METHOD(TestMethod11)
		{
			nums = { 3, 2, 4 }, modulo = 2, k = 1;
			auto res = Solution().countInterestingSubarrays(nums, modulo, k);
			AssertEx(3LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 3,1,9,6 }, modulo = 3, k = 0;
			auto res = Solution().countInterestingSubarrays(nums, modulo, k);
			AssertEx(2LL, res);
		}
	};

	TEST_CLASS(LC1915)
	{
		//LC1915. 最美子字符串的数目
		class Solution {
		public:
			long long wonderfulSubstrings(string word) {
				const int M = 10;
				const int MC = 1 << M;
				long long ans = 0;
				int mask = 0;
				vector<int> cnt(MC);
				cnt[0] = 1;
				for (auto& ch : word) {
					const int cm = 1 << (ch - 'a');
					mask ^= cm;
					ans += cnt[mask];
					for (int j = 0; j < M; j++) {
						ans += cnt[mask ^ (1 << j)];
					}
					cnt[mask]++;
				}
				return ans;
			}
		};
	public:
		string word;
		TEST_METHOD(TestMethod1)
		{
			word = "aba";
			auto res = Solution().wonderfulSubstrings(word);
			AssertEx(4LL, res);
		}
		TEST_METHOD(TestMethod11)
		{
			word = "aabb";
			auto res = Solution().wonderfulSubstrings(word);
			AssertEx(9LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			word = "he";
			auto res = Solution().wonderfulSubstrings(word);
			AssertEx(2LL, res);
		}
	};

	TEST_CLASS(P11293)
	{
		//P11293 [NOISG2022 Qualification] L-Board
		class Solution {
		public:
			long long Ans(vector<vector<int>>& mat) {
				const int R = mat.size();
				const int C = mat[0].size();
				auto Do = [](const vector<vector<int>>& mat) {
					const int R = mat.size();
					const int C = mat[0].size();
					vector<vector<long long>> v1(R, vector<long long>(C, LLONG_MIN / 2));
					auto v2 = v1;
					for (int r = 0; r < R; r++) {
						auto preMax = 0LL;
						for (int c = 0; c < C; c++) {
							v1[r][c] = mat[r][c] + max(preMax, 0LL);
							preMax = v1[r][c];
						}
						auto suffMax = 0LL;
						for (int c = C - 1; c >= 0; c--) {
							v2[r][c] = mat[r][c] + max(suffMax, 0LL);
							suffMax = v2[r][c];
							v2[r][c] = max(v2[r][c], v1[r][c]);							
						}
					}
					return v2;
				};
				auto vlr = Do(mat);
				vector<vector<int>> matRev(C,vector<int>(R));
				for (int r = 0; r < R; r++) {
					for (int c = 0; c < C; c++) {
						matRev[c][r] = mat[r][c];
					}
				}
				auto vtb = Do(matRev);
				auto ans = LLONG_MIN / 2;
				for (int r = 0; r < R; r++) {
					for (int c = 0; c < C; c++) {
						ans = max(ans, vlr[r][c] + vtb[c][r] - mat[r][c]);
					}
				}
				return ans;
			}
		};
	public:
		vector<vector<int>> mat;
		TEST_METHOD(TestMethod1)
		{
			mat = { {8,1},{3,4} };
			auto res = Solution().Ans(mat);
			AssertEx(15LL, res);
		}
		TEST_METHOD(TestMethod11)
		{
			mat = { {-2,-1,8,-2,9,0,-2,1} };
			auto res = Solution().Ans(mat);
			AssertEx(15LL, res);
		}
	};

	TEST_CLASS(P3819)
	{
		//P3819 松江 1843 路
		class Solution {
		public:
			long long Ans(vector<pair<long long,int>> posCnt) {
				const int N = posCnt.size();
				vector<int> preCnt(1);
				vector<long long> preSum(1);
				for (const auto& [x, r] : posCnt) {
					preCnt.emplace_back(preCnt.back() + r);
					preSum.emplace_back(preSum.back() + x * r);
				}
				long long ans = LLONG_MAX / 2;
				for (int i = 0; i < N; i++) {
					const auto dis1 = posCnt[i].first * preCnt[i] - preSum[i];
					const auto dis2 = (preSum.back() - preSum[i + 1]) - posCnt[i].first * (preCnt.back()-preCnt[i+1]);
					ans = min(ans, dis1 + dis2);
				}
				return ans;
			}
		};
	public:
		vector<pair<long long, int>> posCnt;
		TEST_METHOD(TestMethod1)
		{
			posCnt = { {20,3},{50,2},{70,1} };
			auto res = Solution().Ans(posCnt);
			AssertEx(110LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			posCnt = { {0,1},{100,10} };
			auto res = Solution().Ans(posCnt);
			AssertEx(100LL, res);
		}
		TEST_METHOD(TestMethod13)
		{
			posCnt = { {3282894320,391},{4394338332,929},{6932893249,181},{7823822843,440},{9322388365,623} };
			auto res = Solution().Ans(posCnt);
			AssertEx(5473201404068LL, res);
		}
	};

	TEST_CLASS(B4153)
	{
		//B4153 [厦门小学生 C++ 2022] 序列问题|普及+
		class Solution {
		public:
			long long Ans(const string& s) {
				const int N = s.length();
				long long ans = 0;
				int cnt10=0, cnt2 = 0;
				vector<int> v(2*N + 1);
				auto Add = [&](int i) {
					v[i + N]++;
				};
				auto Get = [&](int i) {return v[i + N]; };
				Add(0);
				for (int i = 0; i < N; i++) {
					if ('1' == s[i]) {
						cnt2 += Get(cnt10);
						cnt10++;						
					}
					else {
						cnt10--;
						cnt2 -= Get(cnt10);
					}
					ans += cnt2;
					Add(cnt10);
				}
				return ans;
			}
		};
	public:
		vector<pair<long long, int>> posCnt;
		TEST_METHOD(TestMethod1)
		{
			auto res = Solution().Ans("1");
			AssertEx(1LL, res);
		}
		TEST_METHOD(TestMethod2)
		{
			auto res = Solution().Ans("0");
			AssertEx(0LL, res);
		}
		TEST_METHOD(TestMethod3)
		{
			auto res = Solution().Ans("111");
			AssertEx(6LL, res);
		}
	};

	TEST_CLASS(B4157)
	{
		//【前缀和】B4157 [厦门小学生 C++ 2023] 数据核心| 普及+
		class Solution {
		public:
			vector<long long> Ans(vector<vector<int>>& grid,vector<pair<int,int>>& que) {
				Swap(grid, que);
				const int R = grid.size(), C = grid[0].size();
				vector<vector<long long>> preSum(R, vector<long long>(C + 1));
				for (int r = 0; r < R; r++) {
					for (int c = 0; c < C; c++) {
						preSum[r][c + 1] = preSum[r][c] + grid[r][c];
					}
				}
				vector<vector<long long>> dp2(R, vector<long long>(C,LLONG_MIN/2));
				for (int c = 0; c < C; c++){
					for (int c1 = c; c1 < C; c1++) {
						vector<long long> dp(R);
						dp.back() = preSum.back()[c1 + 1] - preSum.back()[c];
						dp2.back()[c] = max(dp2.back()[c], dp.back());
						for (int r = R - 2; r >= 0; r--) {
							dp[r] = preSum[r][c1 + 1] - preSum[r][c];
							if (dp[r + 1] > 0) { dp[r] += dp[r + 1]; }
							dp2[r][c] = max(dp2[r][c], dp[r]);
						}
					}}
				vector<long long> ans;
				for (const auto& [r, c] : que) {
					ans.emplace_back(dp2[r-1][c-1]);
				}
				return ans;
			}
			void Swap(vector<vector<int>>& grid, vector<pair<int, int>>& que) {
				const int R = grid.size(), C = grid[0].size();
				if (grid.size() > grid[0].size()) { return; }
				vector<vector<int>> tmp(C, vector<int>(R));
				for (int r = 0; r < R; r++) {
					for (int c =0; c < C; c++) {
						tmp[c][r] = grid[r][c];
					}
				}
				tmp.swap(grid);
				for (auto& [x, y] : que) {
					swap(x, y);
				}
			}
		};		
	public:
		vector<vector<int>> grid;
		vector<pair<int, int>> que;
		TEST_METHOD(TestMethod1)
		{
			grid = { {1,-1,1,-1,1},{2,2,2,-1,2},{1,1,2,-1,-1},{-1,-1,2,2,1},{1,1,1,1,-1} },
				que = {{1,1},{2,2},{3,3},{2,4},{5,1},{5,5} }; 
			auto res = Solution().Ans(grid,que);
			AssertEx({ 16,12,7,2,4,-1 }, res);
		}
		TEST_METHOD(TestMethod2)
		{
			grid = { {1,1,1} },
				que = { {1,1} };
			auto res = Solution().Ans(grid, que);
			AssertEx({ 3 }, res);
		}
	};

	TEST_CLASS(P7149)
	{
		//【离散化 二维前缀和】 P7149 [USACO20DEC] Rectangular Pasture S|普及+
		class Solution {
		public:
			long long Ans(vector<pair<int, int>>& pts) {
				const int N = pts.size();
				vector<int> xs, ys;
				for (const auto& [x, y] : pts) {
					xs.emplace_back(x); ys.emplace_back(y);
				}
				CDiscretize<int> disx(xs), disy(ys);
				const int R = disy.size(), C = disx.size();
				vector<vector<int>> mat(R, vector<int>(C));
				for ( auto& [x, y] : pts) {
					x = disx[x]; y = disy[y];
					mat[y][x]++;
				}
				CPreSum2<> preSum(R, C, [&](int r, int c) {return mat[r][c]; });
				sort(pts.begin(), pts.end());
				long long ans = N + 1;
				for (int i = 0; i < N; i++) {
					for (int j = i + 1; j < N; j++) {
						const int y1 = min(pts[i].second,pts[j].second);
						const int y2 = max(pts[i].second,pts[j].second);
						const long long z1 = preSum.Get(pts[i].first,0 , pts[j].first,y1);
						const long long z2 = preSum.Get(pts[i].first, y2, pts[j].first, R-1);
						ans += z1 * z2;
					}
				}
				return ans;
			}
		};
	public:
		vector<pair<int, int>> pts;
		TEST_METHOD(TestMethod1)
		{
			pts = { {0,2},{1,0},{2,3},{3,5} };
			auto res = Solution().Ans(pts);
			AssertEx(13LL, res);
		}
	};

	TEST_CLASS(P8902)
	{
		//【构造 前缀和】P8902 [USACO22DEC] Range Reconstruction S|普及+
		class Solution {
		public:
			vector<int>  Ans(vector<vector<int>>& v2) {
				const int N = v2.size();
				vector<int> a(N);
				a[1] = v2[0][1];
				vector<int> pmin(N,INT_MAX/2), pmax(N,INT_MIN/2);
				pmin[0] = 0, pmin[1] = a[1];
				pmax[0] = a[1] = pmax[1] = a[1];
				for (int i = 2; i < N; i++) {
					const int c = v2[i - 1][1];
					auto Is = [&](int cur)
					{
						for (int j = 0; j < i - 1; j++) {
							if (v2[j][i-j] != max(pmax[j], cur) - min(pmin[j], cur)) {
								return false;
							}
						}
						return true;
					};
					int cur = 0;
					if (Is(a[i - 1] + c)) {
						cur = a[i - 1] + c;
					}
					else {
						cur = a[i - 1] - c;
					}
					a[i] = cur;
					for (int j = 0; j <= i; j++) {
						pmax[j] = max(pmax[j], cur);
						pmin[j] = min(pmin[j], cur);
					}
				}
				return a;
			}
		};
	public:
		vector<vector<int>> a;
		TEST_METHOD(TestMethod1)
		{
			a = { {0,2,2},{0,1},{0} };
			auto res = Solution().Ans(a);
			AssertEx({ 0,2,1 }, res);
		}
		TEST_METHOD(TestMethod2)
		{
			a = { {0,1,1},{0,0},{0} };
			auto res = Solution().Ans(a);
			AssertEx({ 0,1,1 }, res);
		}
		TEST_METHOD(TestMethod3)
		{
			a = { {0,1,2,2},{0,1,1},{0,1},{0} };
			auto res = Solution().Ans(a);
			AssertEx({ 0,1,2,1 }, res);
		}
		TEST_METHOD(TestMethod4)
		{
			a = { {0,1,1,2},{0,0,2},{0,2},{0} };
			auto res = Solution().Ans(a);
			AssertEx({ 0,1,1,-1 }, res);
		}
	};

	TEST_CLASS(P9043)
	{
		//P9043 [PA 2021] Zbalansowane słowa|普及+
		class Solution {
		public:
			long long  Ans(const string& s ) {
				Ans1(s);
				Ans2(s,'a', 'b', 'c');
				Ans2(s, 'c', 'a', 'b');
				Ans2(s, 'b', 'c', 'a');
				Ans3(s);
				return m_ans;
			}
			void Ans1(const string& s) {
				vector<vector<int>> inxs(3, vector<int>(1, -1));
				int k = 0;
				for (const auto& ch : s) {
					const int i = ch - 'a';
					int inx = -1;
					for (int j = 0; j < 3; j++) {
						if (i != j) {
							inx = max(inx, inxs[j].back());
						}
					}
					m_ans += k - inx;
					inxs[i].emplace_back(k);
					k++;
				}
			}
			void Ans3(const string& s) {//包括3种字符
				map<pair<int, int>, int> m;
				m[make_pair(0, 0)] = 1;
				int ab = 0, ac = 0;
				for (int i = 0; i < s.length(); i++) {
					ab -= ('a' == s[i]);
					ab += ('b' == s[i]);
					ac -= ('a' == s[i]);
					ac += ('c' == s[i]);
					m_ans += m[make_pair(ab, ac)];
					m[make_pair(ab, ac)]++;
				}	
			}
			void Ans2(const string& s,const char& ch1,const char& ch2,const char&ch3) {//包括ch1和ch2的数量相等，ch3位0
				map<pair<int, int>, int> m;
				m[make_pair(0, 0)] = 1;
				int ab = 0, ac = 0;
				for (int i = 0; i < s.length(); i++) {
					ab -= (ch1 == s[i]);
					ab += (ch2 == s[i]);					
					ac += (ch3 == s[i]);
					m_ans += m[make_pair(ab, ac)];
					m[make_pair(ab, ac)]++;
				}
			}
			long long m_ans = 0;
		};
	public:
		TEST_METHOD(TestMethod1)
		{
			auto res = Solution().Ans("aabbabcccba");
			AssertEx(28LL, res);
		}
	};

	TEST_CLASS(P9186)
	{
		//【前缀和 二分查找】P9186 [USACO23OPEN] Milk Sum S|普及+
		class Solution {
		public:
			vector<long long>  Ans(const vector<int>& a,const vector<pair<int,int>>& que) {
				auto b = a;
				sort(b.begin(), b.end());
				vector<long long> preSum(1);
				for (const auto& i : b) {
					preSum.emplace_back(preSum.back() + i);
				}
				long long T = 0;
				for (int i = 0; i < b.size(); i++) {
					T += (long long)b[i] * (i + 1);
				}
				vector<long long> ans;
				for (const auto& [i, j] : que) {
					long long cur = T;
					const auto i1 = lower_bound(b.begin(), b.end(), a[i - 1])-b.begin();
					cur -= (long long)b[i1] * i1;
					cur -= (preSum.back() - preSum[i1]);
					const auto j1 = upper_bound(b.begin(), b.end(), j) - b.begin();
					cur += (preSum.back() - preSum[j1]);
					cur += (long long)j * (j1 + 1-(i1 < j1));
					if (i1 >= j1) {
						cur -= b[i1];
					}
					ans.emplace_back(cur);
				}
				return ans;
			}
		};
	public:
		vector<int> a;
		vector<pair<int, int>> que;
		TEST_METHOD(TestMethod1)
		{
			que = { {2,1},{2,8},{4,5} }, a = { 1,10,4,2,6 };
			auto res = Solution().Ans(a,que);
			AssertEx({ 55LL,81LL,98LL }, res);
		}
	};

	TEST_CLASS(LC3714)
	{//【前缀和 分类讨论】3714. 最长的平衡子串 II|未知分数
		class Solution {
		public:
			int longestBalanced(string s) {
				map<pair<int, int>, int> mABC;
				map<int, int> mAB, mBC, mAC;
				mABC[make_pair(0, 0)] = -1;
				mAB[0] = -1;
				mBC[0] = -1;
				mAC[0] = -1;
				int ans = 1, a = 0, b = 0, c = 0;
				int aleft = -1, bleft = -1, cleft = -1;
				for (int i = 0;i < s.length();i++) {
					if ('a' == s[i]) { a++; mBC.clear(); }
					else if ('b' == s[i]) { b++;mAC.clear(); }
					else { c++; mAB.clear(); }
					auto abc = make_pair(b - a, c - a);
					auto  ab = b - a;
					auto ac = c - a;
					auto bc = c - b;
					if (mABC.count(abc)) {
						ans = max(ans, i - mABC[abc]);
					}
					else {
						mABC[abc] = i;
					}
					if (mAB.count(ab)) {
						ans = max(ans, i - mAB[ab]);
					}
					else {
						mAB[ab] = i;
					}
					if (mBC.count(bc)) {
						ans = max(ans, i - mBC[bc]);
					}
					else {
						mBC[bc] = i;
					}
					if (mAC.count(ac)) {
						ans = max(ans, i - mAC[ac]);
					}
					else {
						mAC[ac] = i;
					}
				}
				ans = max(ans, Do1(s));
				return ans;
			}
			int Do1(string& s) {
				vector<pair<char, int>> leftLen;
				int ans = 0;
				for (const auto& ch : s) {
					if (leftLen.size() && (ch == leftLen.back().first)) {
						leftLen.back().second++;
					}
					else {
						leftLen.emplace_back(ch, 1);
					}
					ans = max(ans, leftLen.back().second);
				}
				return ans;
			}
		};
	public:
		string s;

		TEST_METHOD(TestMethod11)
		{
			s = "abbac";
			auto res = Solution().longestBalanced(s);
			AssertEx(4, res);

		}
		TEST_METHOD(TestMethod12)
		{
			s = "aabcc";
			auto res = Solution().longestBalanced(s);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod13)
		{
			s = "aba";
			auto res = Solution().longestBalanced(s);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod14)
		{
			s = "aaaabc";
			auto res = Solution().longestBalanced(s);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod15)
		{
			s = "abbbbc";
			auto res = Solution().longestBalanced(s);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod16)
		{
			s = "abcccc";
			auto res = Solution().longestBalanced(s);
			AssertEx(4, res);
		}
	};

	TEST_CLASS(LC3729)
	{//【动态规划 组合数学 前缀和】3729. 统计有序数组中可被 K 整除的子数组数量|分数未知
		class Solution {
		public:
			long long numGoodSubarrays(vector<int>& nums, int K) {
				vector<pair<int, int>> valCnt;
				for (const auto& n : nums) {
					if (valCnt.size() && (n == valCnt.back().first)) { valCnt.back().second++; }
					else { valCnt.emplace_back(n, 1); }
				}
				unordered_map<int, long long> pre;
				pre[0] = 1;
				long long ans = 0;
				{
					int sum = 0;
					for (const auto& n : nums) {
						sum = (sum + n) % K;
						ans += pre[sum];
						pre[sum]++;
					}
				}
				for (const auto& [val, cnt] : valCnt) {
					int sum = 0;
					for (int c = 1; c <= cnt;c++) {
						sum = (sum + val) % K;
						if (0 == sum) {
							ans -= (cnt - c);
						}
					}
				}
				return ans;
			}
		};
	public:
		vector<int> nums;
		int k;
		class Solution2 {
		public:
			long long numGoodSubarrays(vector<int>& nums, int K) {
				vector<pair<int, int>> valCnt;
				for (const auto& n : nums) {
					if (valCnt.size() && (n == valCnt.back().first)) { valCnt.back().second++; }
					else { valCnt.emplace_back(n, 1); }
				}
				unordered_map<int, long long> pre;
				long long ans = 0;
				for (const auto& [val, cnt] : valCnt) {
					pre[0]++;
					for (const auto& [sum, cnt2] : pre) {
						for (int c = 1; c <= cnt;c++) {
							const int sum1 = (sum + (long long)val * c) % K;
							if (0 == sum1) { ans += cnt2; }
						}
					}
					unordered_map<int, long long> cur;
					for (const auto& [sum, cnt2] : pre) {
						const int sum1 = (sum + (long long)val * cnt) % K;
						cur[sum1] += cnt2;
					}
					for (int c = 1; c < cnt;c++) {
						cur[(long long)val * c % K]++;
					}
					pre.swap(cur);
				}
				return ans;
			}
		};
		TEST_METHOD(TestMethod11)
		{
			nums = { 1,2,3 }, k = 3;
			auto res2 = Solution2().numGoodSubarrays(nums, k);
			AssertEx(3LL, res2);
			auto res = Solution().numGoodSubarrays(nums, k);
			AssertEx(res2, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 2,2,2,2,2,2 }, k = 6;
			auto res2 = Solution2().numGoodSubarrays(nums, k);
			AssertEx(2LL, res2);
			auto res = Solution().numGoodSubarrays(nums, k);
			AssertEx(res2, res);
		}
		TEST_METHOD(TestMethod13)
		{
			nums = { 7,8,9,9,10,11,11,13 }, k = 6;
			auto res2 = Solution2().numGoodSubarrays(nums, k);
			auto res = Solution().numGoodSubarrays(nums, k);
			AssertEx(res2, res);
		}
		TEST_METHOD(TestMethod14)
		{
			nums = { 2,2,2,2,2,2,4,4,4,5,7,8,9,9,9,10,10,11,11,13 }, k = 6;
			auto res2 = Solution2().numGoodSubarrays(nums, k);
			auto res = Solution().numGoodSubarrays(nums, k);
			AssertEx(res2, res);
		}
		TEST_METHOD(TestMethod15)
		{
			nums = { 1,1,1,1,1,2,2,2,2,2,2,4,4,4,5,7,8,9,9,9,10,10,11,11,13,14,14,14,14,14,15,15,16,17,18 }, k = 5;
			auto res2 = Solution2().numGoodSubarrays(nums, k);
			auto res = Solution().numGoodSubarrays(nums, k);
			AssertEx(res2, res);
		}
		TEST_METHOD(TestMethod16)
		{
			nums = { 1,1,1,1,1,2,2,2,2,2,2,4,4,4,5,7,8,9,9,9,10,10,11,11,13,14,14,14,14,14,15,15,16,17,18,18,20,20,20,20,20,20,21,21,21 }, k = 2;
			auto res2 = Solution2().numGoodSubarrays(nums, k);
			auto res = Solution().numGoodSubarrays(nums, k);
			AssertEx(res2, res);
		}
		TEST_METHOD(TestMethod17)
		{
			nums = { 1,1,1,1,1,2,2,2,2,2,2,4,4,4,5,7,8,9,9,9,10,10,11,11,13,14,14,14,14,14,15,15,16,17,18,18,20,20,20,20,20,20,21,21,21,23 }, k = 1;
			auto res2 = Solution2().numGoodSubarrays(nums, k);
			auto res = Solution().numGoodSubarrays(nums, k);
			AssertEx(res2, res);
		}
		TEST_METHOD(TestMethod18)
		{
			k = 1;
			nums.clear();
			for (int i = 0;i < 1000;i++) {
				nums.emplace_back(1e9 - i);
			}
			auto res2 = Solution2().numGoodSubarrays(nums, k);
			auto res = Solution().numGoodSubarrays(nums, k);
			AssertEx(res2, res);
		}
	};

	TEST_CLASS(LC3728)
	{//【前缀和】3728. 边界与内部和相等的稳定子数组|未知分数
		class Solution {
		public:
			long long countStableSubarrays(vector<int>& capacity) {
				vector<long long> preSum = { 0 };
				for (const auto& n : capacity) {
					preSum.emplace_back(preSum.back() + n);
				}
				unordered_map<int, unordered_map<long long, int>> inx;
				long long ans = 0;
				for (int j = 2; j < capacity.size();j++) {
					const int i = j - 2;
					const long long sum = preSum[i] + capacity[i] * 3LL;
					inx[capacity[i]][sum]++;
					ans += inx[capacity[j]][preSum[j + 1]];
				}
				return ans;
			}
		};
	public:
		vector<int> capacity;

		TEST_METHOD(TestMethod11)
		{
			capacity = { 9, 3, 3, 3, 9 };
			auto res = Solution().countStableSubarrays(capacity);
			AssertEx(2LL, res);
		}
		TEST_METHOD(TestMethod12)
		{
			capacity = { 1,2,3,4,5 };
			auto res = Solution().countStableSubarrays(capacity);
			AssertEx(0LL, res);
		}
		TEST_METHOD(TestMethod13)
		{
			capacity = { -4,4,0,0,-8,-4 };
			auto res = Solution().countStableSubarrays(capacity);
			AssertEx(1LL, res);
		}
	};

	TEST_CLASS(LC3748)
	{//【分治法 前缀和】3748. 统计稳定子数组的数目|分数未知
		class Solution {
		public:
			vector<long long> countStableSubarrays(vector<int>& nums, vector<vector<int>>& queries) {
				const int N = nums.size();
				vector<int> inxs = { 0 };
				for (int i = 1; i < N; i++) {
					if (nums[i - 1] > nums[i]) {
						inxs.emplace_back(i);
					}
				}
				inxs.emplace_back(N);
				auto Cnt = [&](long long len) {
					return (1 + len) * len / 2;
				};
				vector<long long> cnts;
				for (int i = 1; i < inxs.size(); i++) {
					cnts.emplace_back(Cnt(inxs[i] - inxs[i - 1]));
				}
				vector<long long> preSum = { 0 };
				for (const auto& n : cnts) {
					preSum.emplace_back(preSum.back() + n);
				}
				vector<long long> ans;
				for (const auto& v : queries) {
					const auto inx1 = upper_bound(inxs.begin(), inxs.end(), v[0]) - inxs.begin() - 1;
					const auto inx2 = upper_bound(inxs.begin(), inxs.end(), v[1]) - inxs.begin() - 1;
					if (inx1 == inx2) {
						ans.emplace_back(Cnt(v[1] - v[0] + 1)); continue;
					}
					const auto l1 = Cnt(inxs[inx1 + 1] - v[0]);
					const auto l2 = preSum[inx2] - preSum[inx1 + 1];
					const auto l3 = Cnt(v[1] - inxs[inx2] + 1);
					ans.emplace_back(l1 + l2 + l3);
				}

				return ans;
			}
		};
	public:
		vector<int> nums;
		vector<vector<int>> queries;

		TEST_METHOD(TestMethod11)
		{
			nums = { 3,1,2 }, queries = { {0,1},{1,2},{0,2} };
			auto res = Solution().countStableSubarrays(nums, queries);
			AssertEx({ 2,3,4 }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 2,2 }, queries = { {0,1},{0,0} };
			auto res = Solution().countStableSubarrays(nums, queries);
			AssertEx({ 3,1 }, res);
		}
	};

	TEST_CLASS(LC3756)
	{//【前缀和】3756. 连接非零数字并乘以其数字和 II|分数未知
		typedef C1097Int<> BI;
		class Solution {
		public:
			vector<int> sumAndMultiply(string s, vector<vector<int>>& queries) {
				vector<int> cntPreSum(1), sumPreSum(1);
				vector<BI> xPreSum(1);
				for (const auto& ch : s) {
					const int i = ch - '0';
					cntPreSum.emplace_back(cntPreSum.back() + (i > 0));
					sumPreSum.emplace_back(sumPreSum.back() + i);
					BI cur = (0 == i) ? xPreSum.back() : (xPreSum.back() * 10 + i);
					xPreSum.emplace_back(cur);
				}
				vector<int> ans;
				for (const auto& v : queries) {
					const int bit = cntPreSum[v[1] + 1] - cntPreSum[v[0]];
					BI cur = xPreSum[v[1] + 1] - xPreSum[v[0]] * BI(10).pow(bit);
					cur *= sumPreSum[v[1] + 1] - sumPreSum[v[0]];
					ans.emplace_back(cur.ToInt());
				}
				return ans;
			}
		};
	public:
		string s;
		vector<vector<int>> queries;

		TEST_METHOD(TestMethod11)
		{
			s = "10203004", queries = { {0,7},{1,3},{4,6} };
			auto res = Solution().sumAndMultiply(s, queries);
			AssertEx({ 12340, 4, 9 }, res);
		}
		TEST_METHOD(TestMethod12)
		{
			s = "1000", queries = { {0,3},{1,1} };
			auto res = Solution().sumAndMultiply(s, queries);
			AssertEx({ 1,0 }, res);
		}

		TEST_METHOD(TestMethod13)
		{
			s = "9876543210", queries = { {0,9} };
			auto res = Solution().sumAndMultiply(s, queries);
			AssertEx({ 444444137 }, res);
		}
	};
}
